Teoría (9 ptos)

1. (1 punto) Defina brevemente qué es un traductor.
2. (1 punto) Defina brevemente qué es un intérprete.
3. (2 puntos) Enumere las fases de un compilador indicando brevemente la función de cada una de ellas.
4. (1 punto) Indique la diferencia entre componente léxico y lexema.
5. Dada la siguiente definición:

   L(G) = { w ∈ Σ^* | S ⇒⁺ w},

   indique el significado de:
   1. L(G)
   2. w
   3. Z
   4. S ⇒⁺ w
6. (2 puntos) Clasifique cada una de las siguientes gramáticas de acuerdo a la Jeraquía de Chomsky.
   1. S → aSbS | bSaS | ε
   2. S → aSB | aB
      a B → aB | ab
      bB → bB | bb
   3. S → aR | a
      R → bR | b
   4. S → ( L ) | a
      L → S,L | S
      
7. ¿Qué tipo de analizador sintáctico genera la herramienta ANTLR?
   
8. ¿Porqué es necesario eliminar la recursión izquierda para escribir un Analizador Sintáctico Descendente para la gramática?
   

Práctica (11 puntos)

1. (1 punto) Construya una expresión regular para el siguiente lenguaje:

   L={w ∈ {a,b}^* | la subsecuencia aab aparece en w}

   
   

2. (2 puntos) Construya una expresión regular para el siguiente lenguaje:

   L={w ∈ {a,b}^* | la subsecuencia aab no aparece en w}

   
   

3. Escriba una gramática independiente del contexto que genere el mismo lenguaje descrito por la expresión regular c(a|b)^*c.
   

   con variaciones en los otros dos exámenes: (a|c)*ac y ab(b|c)*

   .
   Dada la siguiente gramática

   variación de ejercicio 4.2 del libro

   S → A | B
   A → pSqS
   B → qSpS | ε

   
   

4. Demuestre que la gramática del ejercicio anterior es ambigua produciendo dos derivaciones izquierdas para la frase pqpq

   qpqp en otro examen, y pqqp en el otro. Cortas para que sea fácil corregirlas.

   .
   
   

5. Construya los árboles de derivación correspondientes a las respuestas de la pregunta anterior.
   
   
6. Considere el lenguaje de las direcciones Internet (URL). Cada una de esas cadenas está compuesta por:
   • Opcional: El nombre de un protocolo seguido de dos puntos.
   • Opcional: El nombre de un servidor, precedido de dos barras ( // ).
   • Opcional: Un paso, que es una secuencia de nombres separados por barras ( / ).
   1. (2 puntos) Escriba una gramática independiente del contexto para el lenguaje descrito.
   2. (4 puntos) Escriba en ANTLR las definiciones léxicas y sintácticas para el ejercicio anterior
      
   3. (4 puntos) Escriba en el lenguaje de programación Java un analizador sintáctico recursivo descendente con retroceso que reconozca el lenguaje generado por la gramática de la respuesta anterior. Asuma que tiene disponible un analizador léxico con las siguientes características:

interface Lexico
{
    /**
     * Avanza la entrada hasta el siguiente componente léxico.
     */
    void avanza();

    /**
     * Retorna el componente léxico en la posición actual
     */
    String actual();

    /**
     * Compara actual con el parámetro c. Llama a avanza y retorna true si son
     * iguales. Retorna false de lo contrario.
     */
    boolean consume(String c);

    /*
     * { if (c.equals(actual)) { avanza(); return true; } return false; }
     */

    /**
     * Regresa true si se agotó la secuencia de entrada, false de lo contrario.
     */
    boolean fin();

    /**
     * regresa el lexema asociado al componente léxico retornado por actual
     */
    String lexema();

    /**
     * Regresa la posición actual en la entrada.
     */
    int posicion();

    /**
     * Cambia la posición actual en la entrada.
     */
    void cambiarPosicion(int nuevaPosicion);
}